#include <string>
#include <vector>
using namespace std;

void backtrace(string &digits, int cur, vector<string> &res, string &selected) {
  if (selected.size() == digits.size()) {
    res.push_back(selected);
    return;
  }
  int cur_digit = digits[cur] - '0';
  if (cur_digit == 9) {
    for (int i = 0; i < 4; ++i) {
      char c = 'a' + (cur_digit - 2) * 3 + i + 1;
      selected += c;
      backtrace(digits, cur + 1, res, selected);
      selected.pop_back();
    }
  } else if (cur_digit == 7) {
    for (int i = 0; i < 4; ++i) {
      char c = 'a' + (cur_digit - 2) + i;
      selected += c;
      backtrace(digits, cur + 1, res, selected);
      selected.pop_back();
    }
  } else {
    for (int i = 0; i < 3; ++i) {
      char c;
      if (cur_digit == 8) {
        c = 'a' + (cur_digit - 2) + i + 1;
      } else {
        c = 'a' + (cur_digit - 2) + i;
      }
      selected += c;
      backtrace(digits, cur + 1, res, selected);
      selected.pop_back();
    }
  }
}

vector<string> letterCombinations(string digits) {
  if (digits.empty()) {
    return {};
  }
  vector<string> res;
  string selected;
  backtrace(digits, 0, res, selected);
  return res;
}